﻿using System;

namespace LightsOutProblem
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			Console.WriteLine ("Hi, Square Lights out problem !");
			int n;
			Console.Write ("请输入正方形的边长:\t");
			while((n=int.Parse(Console.ReadLine())) > 0){

				int[,] puzzle = new int[n + 1, n + 2];
				int[,] press = new int[n + 1, n + 2];
//				for (int r = 0; r < n + 1; r++) {
//					press [r, 0] = press [r, n + 1] = 0;
//				}
//				for (int c = 1; c < n + 1; c++) {
//					press [0, c] = 0;
//				}
				
				//初始化一个n*n的亮灯矩阵
				for (int r = 1; r < n + 1; r++) {
					for (int c = 1; c < n + 1; c++) {
						puzzle [r, c] = 1;
					}
				}
				
				Enumate (press,puzzle,n);
				
				//输出
				for (int r = 1; r < n + 1; r++) {
					for (int c = 1; c < n + 1; c++) {
						Console.Write (press[r,c]+" ");
					}
					Console.WriteLine ();
				}

				Console.Write ("请再次输入边长:\t");

			}
		}

		public static void Enumate(int[,] press, int[,] puzzle, int n){
			int c;
//			for (c = 1; c < n + 1; c++)
//				press [1, c] = 0;

			/*
			 * 对press第一行的元素press[1,1]~press[1,n]的各种取值情况进行枚举,
			 * 在每种取值情况下,分别调用guess(),看看是否找到了答案.
			 */
			while(!guess(n,press,puzzle)){
				press [1, 1]++;
				c = 1;
				while (press [1, c] > 1) {
					press [1,c] = 0;
					c++;
					press [1, c]++;
				}
			}
			return;
		}

		public static bool guess(int n,int[,] press,int[,] puzzle){
			/*
			 * 根据press第一行和puzzle矩阵,按照熄灯规则计算出press其他行的值,
			 * 使得矩阵第1 ~ n-1行的所有灯都熄灭
			 */
			for (int r = 1; r < n; r++) {
				for (int c = 1; c < n + 1; c++) {
					press [r + 1, c] = (puzzle [r, c] + press [r, c] + press [r, c - 1] + press [r, c + 1] + press [r - 1, c]) % 2;
				}
			}

			/*
			 * 判断说计算的press数组能否熄灭矩阵第n行的所有灯,
			 * 如果能够就返回true,表示找到了答案,否则返回false表示没有找到答案. 
			 */
			for (int c = 1; c < n + 1; c++) {
				if((press[n,c] + press[n,c-1] + press[n,c+1] + press[n-1,c])%2 != puzzle[n,c]){  
					return false;
				} 
			}
			return true;
		}

	}
}
